package leetcode.双指针法;

import java.util.*;

/**
 * todo 三数之和
 * <p>
 * 先对数组按升序排序：-2,-1,0,1,2
 * 设置三个指针，i、j、k
 * 初始时：i、j指向最前面的数据，k指向最后面的数据
 * 因此核心思想就是希望出现这种情况 i + j 的值能够与 k 的值刚好相反
 * <p>
 * 于是我们必须构造这种期待的情况
 */
public class Test15三数之和 {

    // 递归失败了
    public static List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length < 3) {
            return ans;
        }
        List<Integer> tmp = new ArrayList<>();
        tmp.add(nums[0]);
        backTrack(ans, tmp, nums, nums[0], 1);
        if (ans.size() != 0) {
            ans.stream().forEach(e -> e.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            }));
            HashSet hashSet = new HashSet(ans);
            ans.clear();
            ans.addAll(hashSet);
        }
        return ans;
    }

    public static void backTrack(List<List<Integer>> ans, List<Integer> tmp,
                                 int[] nums, int x, int index) {
        if (tmp.size() == 3 && x == 0) {
            ans.add(new ArrayList<>(tmp));
        }
        for (int i = index; i < nums.length; i++) {
            // 去重
//            if () {
//                continue;
//            }
            tmp.add(nums[i]);
            backTrack(ans, tmp, nums, x + nums[i], index + 1);
            tmp.remove(tmp.size() - 1);
        }

    }

    /**
     * 三指针法
     * 每次固定 i
     * 然后移动 j、k 寻找正确的 i、j、k 组合
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length < 3) {
            return ans;
        }
        // 先对其顺序排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                // 先计算总和，然后根据计算结果处理i、j、k的移动
                int result = nums[i] + nums[j] + nums[k];
                if (result == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                    // 排除最右边指针下一次指向相同的数据
                    /*
                    为什么不用 if 语句？
                    因为如果是 0,0,0,0,0
                    if语句只会执行一次，执行完后k指针指向的数据和之前的还是一样的
                    所以要循环执行
                     */
                    while (j < k && nums[k] == nums[k - 1]) {
                        k--;
                    }
                    // 排除左边i指针下一次指向相同的数据
                    while (j < k && nums[j] == nums[j + 1]) {
                        j++;
                    }
                    // 不管是否需要排除重复的情况，当前j或k指向的还是 那个值，要再次++或--
                    j++;
                    k--;
                } else if (result < 0) {
                    // 结果小于0说明，负数值太大了，导致正数不够平衡它，原因就在于j指向的负数太小，需要扩大它
                    while (j < k && nums[j] == nums[j + 1]) {
                        j++;
                    }
                    j++;
                } else {
                    // 结果大于0说明，正数值太大了，导致负数数不够平衡它，原因就在于k指向的正数太大，需要缩小它
                    while (j < k && nums[k] == nums[k - 1]) {
                        k--;
                    }
                    k--;
                }
            }
            // 本次循环结束后，i需要自增1，但是如果自增后值重复了怎么办？所以依然需要去重，让i跳过相同的值
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        long start = System.currentTimeMillis();
//        int[] num = new int[] {-1, 0, 1, 2, -1, -4};
//        int[] num = new int[] {0,0,0,0};
        int[] num = new int[]{1, -1, -1, 0};
        System.out.println(threeSum(num));
        long end = System.currentTimeMillis();
        System.out.println(end - start + "ms");
    }
}
